package binaryTree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/*
 *@description
 *@author hkfan
 *@version 1.0
 *@create 2025/6/16 15:36
 */
public class LeetCode_103 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        //1. 特殊情况
        if (root==null){
            return new ArrayList<>();
        }
        //2. 定义
        Boolean inverseList =false;
        Queue<TreeNode> queue = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
        //3. 初始化
        queue.add(root);
        queue.add(null);
        //4. 循环
        while (!queue.isEmpty()){
            Boolean flag = false;
            TreeNode node = queue.poll();
            if (node==null){
                continue;
            }
            if ((!queue.isEmpty())&& queue.peek()==null){
                list.add(node.val);
                addList(res,list,inverseList);
                inverseList=!inverseList;
                list=new ArrayList<>();
                flag=true;
            }
            if ((!queue.isEmpty())&& queue.peek()!=null){
                list.add(node.val);

            }
            if (node.left!=null){
                queue.add(node.left);
            }
            if (node.right!=null){
                queue.add(node.right);
            }
            if (flag){
                queue.add(null);
            }


        }
        return res;
    }

    private void addList(List<List<Integer>> res, List<Integer> list, Boolean inverseList) {
        if (!inverseList){
            res.add(list);
        }else {
            ArrayList<Integer> tempList = new ArrayList<>();
            for (int i = list.size()-1; i >=0 ; i--) {
                tempList.add(list.get(i));
            }
            res.add(tempList);
        }
    }

}
